package com.atguigui.leetcode;

/**
 * 481.神奇字符串
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/10/31 9:08
 */
public class P481MagicalString {

    public static void main(String[] args) {
        Solution solution = new P481MagicalString().new Solution();
        // TO TEST
    }

    class Solution {
        public int magicalString(int n) {
            if (n < 4) {
                return 1;
            }
            char[] s = new char[n];
            s[0] = '1';
            s[1] = '2';
            s[2] = '2';
            int res = 1;    //结果
            int i = 2;      //左指针
            int j = 3;      //右指针
            while (j < n) {
                int size = s[i] - '0';
                int num = 3 - (s[j - 1] - '0'); //判断是0还是1
                while (size > 0 && j < n) {
                    s[j] = (char) ('0' + num);
                    if (num == 1) {
                        res++;
                    }
                    ++j;
                    --size;   //退出循环
                }
                i++;
            }
            return res;
        }
    }
}
